package j2024.j202408;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class j0816 {
    /**
     * 413. 等差数列划分
     * @param nums
     * @return
     */
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int sum = 0;
        for (int i = 2; i < n; i++) {
            dp[i] =  nums[i]-nums[i-1]==nums[i-1]-nums[i-2]?dp[i-1]+1:0;
            sum+=dp[i];
        }
        return sum;
    }

    /**
     * 978. 最长湍流子数组
     * @param arr
     * @return
     */
    public int maxTurbulenceSize(int[] arr) {
        int n =arr.length;
        int[] f =new int[n];
        int[] g =new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            g[i] = 1;
        }
        int ret = 1;
        for (int i = 1; i < n; i++) {
            if(arr[i]>arr[i-1]){
                f[i] = g[i-1]+1;
            }else if(arr[i]<arr[i-1]){
                g[i] = f[i-1]+1;
            }
            ret = Math.max(ret,Math.max(f[i],g[i]));

        }
        return ret;
    }

    /**
     * 139. 单词拆分
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        s = " "+s;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j >=1 ; j--) {
                if(dp[j-1] && set.contains(s.substring(j,i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    /**
     * 467. 环绕字符串中唯一的子字符串
     * @param s
     * @return
     */
    public int findSubstringInWraproundString(String s) {
        int n =s.length();
        char[] str = s.toCharArray();
        int[] dp = new  int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if(str[i-1]+1==str[i]  || (str[i-1]=='z'  && str[i]=='a')){
                dp[i]+=dp[i-1];
            }
        }
        int[] hash = new int[26];
        for (int i = 0; i < n; i++) {
            hash[str[i]-'a'] = Math.max(hash[str[i]-'a'],dp[i]);
        }
        int ret =  0;
        for (int i = 0; i < 26; i++) {
            ret+=hash[i];
        }
        return ret;
    }

    /**
     * 300. 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
         int n = nums.length;
         int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int ret  =1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
                ret = Math.max(ret,dp[i]);
            }
        }
        return ret;
    }

    /**
     * 376. 摆动序列
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g =new int[n];
        for (int i = 0; i < n; i++) {
            f[i] =g[i] =1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i]>nums[j]){
                    f[i] = Math.max(f[i],g[j]+1);
                }else if(nums[i]<nums[j]){
                    g[i] = Math.max(g[i],f[j]+1);
                }
            }
        }
        int ret  = 1;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret,Math.max(f[i],g[i]));
        }
        return ret;
    }

    /**
     * 673. 最长递增子序列的个数
     * @param nums
     * @return
     */
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = count[i] =1;
        }
        int retlen =1,retcount = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[j]<nums[i]){
                    if(len[j]+1==len[i]){
                        count[i]+=count[j];
                    }else if(len[j]+1>len[i]){
                        count[i] = count[j];
                        len[i] = len[j]+1;
                    }
                }
            }
            if(retlen==len[i]){
                retcount+=count[i];
            }else if(retlen<len[i]){
                retcount= count[i];
                retlen  = len[i];
            }

        }
        return retcount;
    }

    /**
     * 646. 最长数对链
     * @param pairs
     * @return
     */
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.sort(pairs,(a,b)->a[0]-b[0]);
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        int ret = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if(pairs[i][0]>pairs[j][1]){
                    dp[i] =  Math.max(dp[i],dp[j]+1);
                }
                ret = Math.max(ret,dp[i]);
            }
        }
        return ret;
    }

    /**
     * 1218. 最长定差子序列
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        int ret = 0;
        for(int a:arr){
            map.put(a,map.getOrDefault(a-difference,0)+1);
            ret = Math.max(ret,map.get(a));
        }
        return ret;
    }

    /**
     * 873. 最长的斐波那契子序列的长度
     * @param arr
     * @return
     */
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(arr[i],i);
        }
        int[][] dp= new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 2;
            }
        }
        int ret  =2;
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                int a = arr[i]-arr[j];
                if(map.containsKey(a) && a<arr[j]){
                    dp[j][i]  = dp[map.get(a)][j]+1;
                    ret = Math.max(ret,dp[j][i]);
                }
            }
        }
        return ret<3?0:ret;
    }
}
